#include <iostream>
#include <vector>
#include <algorithm>
#include <queue> 
using namespace std;

// 这里还需要在1后面加上LL来防止窝里溢出
const long long INF = (1LL<<31)-1;
// 首先这一步我就够呛研究出来

struct Node
{
    int id;
    long long dist;
    Node(int i,long long d): id(i),dist(d){};

    bool operator>(const Node&n1)
    {
        return this->dist > n1.dist; 
    }
};

struct Edge 
{
    int to;
    long long weight;
    Edge(int t,long long w) :to(t),weight(w){};
};

vector<long long> dijistra(int n ,int s,vector<vector<Edge>>&graph)
{   
    // 首先假设所有距离均为正无穷(完全非连通)
    vector<long long> dist(n+1,INF);
    vector<bool>visited(n,false);   // 广度优先算法必备

    // 使用最小堆？？？始终暴露距离id == s节点的距离最大值的节点
    priority_queue<Node ,vector<Node>,greater<Node>>pq;

    // 因为s 到 s 的距离一定为0所以先赋值为0
    dist[s] = 0;
    
    // 这一步往队列中push第一个元素没看懂
    // 由于使用优先队列遍历节点，因此以
    pq.push(Node(s,0));

    // 运用广度优先遍历算法
    while (!pq.empty())
    {
        // 每次循环面向队列首元素编程
        Node temp = pq.top();
        pq.pop();

        // 再用临时变量标记temp.id防止代码过长
        int u = temp.id;
        if (visited[u])
        {
            continue;
        }
        // 这里就是应该这么使用visited数组进行防止重复访问
        visited[u] = true;

        // 核心逻辑部分
        // 对于每一个节点，遍历他伸出去的每一条边
        for (const Edge &edge :graph[u])
        {
            // 这里使用const 是防止edge发生更改
            // 使用&是为了防止直接复制一份
            int v = edge.to;
            long long w = edge.weight;

            // 这里其实还是需要进行判断是否访问？？？不懂
            // 如果三角形两边之和小于第三边，说明这个可以更新为s到这个节点的新距离
            if (!visited[u]&&dist[u]+w < dist[v])
            {
                // 这里由于先到u再到edge.to的距离之和小于直接到edge.to的距离，因此将距离更新为
                // 看看能不能通过让路径通过经过该节点的方式，把整个路径进行缩短
                dist[v] = dist[u]+w;
                // 然后将v,的相关数据使用Node封装好，加入队列
                // 这一步是在捞还未遍历的节点
                pq.push(Node(v,dist[v]));
                // 这一步是继续处理其他节点
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m,s;
    cin>>n>>m>>s;

    vector<vector<Edge>> graph(n+1);

    for (int i = 0;i < m;i++)
    {
        int u,v;
        long long w;
        cin>>u>>v>>w;
        graph[u].push_back(Edge(v,w));
    }

    // 准备输出结果
    vector<long long>dist = dijistra(n,s,graph);

    for (auto i :dist)
    {
        cout<<i<<"\n";
    }
    return 0;
}